Embodiments of the present invention generally relate to wireless sensor networks and relate more particularly to methods and systems that implement a series-parallel channel hopping scheme in a wireless sensor network.
Multi-tiered wireless sensor networks (WSNs) exist that are distributed over large geographic areas. Conventional multi-tier wireless sensor networks include a main node (e.g. a coordinator node, or gateway node) that forms a first tier. The main node is logically linked to nodes in a second tier. The nodes in the second tier may be end nodes or repeater nodes. Repeater nodes in a second tier may be logically linked to one or more end-nodes that are in a third tier. The entire collection of end-nodes may comprise a third tier of the network. The IEEE 802.15.4 protocol standard, Version 2 (2006) distinguishes between “fully functional nodes” and “partially functional nodes”. Other times nodes are designated using a parent-child relationship (e.g., with the “parent” being a fully functional node such as the main node or a repeater node, and the “child” being a partially functional node such as an end-node). The relationship between the main node and a repeater node may also be referred to as a parent-child relationship, with the repeater serving the subordinate role. Oftentimes the fully-functional nodes, which serve, or are capable of serving as parent nodes, use higher receiver sensitivities and transmitter powers and better channel isolation (i.e., better radios), while end-nodes (which virtually always fill the role of children nodes and are much more numerous in the network) use less costly radios with generally poorer performance. The network described above is in general spread out over a large physical area. For example, two nodes (at least one of which has a low-noise amplifier and power amplifier) can communicate with each other over a distance of several hundred feet with little difficulty, and thus the entire network may cover an area of 100,000 square feet or more, and multiple floors of a building. More general network topologies also exist in which the various network tiers are organized or organize themselves in ad hoc fashion, based on quality of communications links between the various pair combinations of nodes, as determined in tests conducted during the ad hoc network formation. Regardless of the actual network topology, it can be stated that in most practical WSN implementations a given end node (e.g., tier N) finds itself connected solely to some “parent” node one tier above (e.g. tier N-1).
Generally, a wireless sensor network uses channels or frequency ranges spread throughout a larger frequency range prescribed by means, such as governmental regulation. For instance, in the United States a wireless sensor network operating in the 902-928 MHz range may use a set of channels up to 50 in number. Furthermore, the network uses those channels in “random hopping” fashion, such that nodes communicate over a particular channel for only a short period of time (typically a few tenths of a second), before hopping/jumping to another channel. The order of channel occupancy is random, or apparently random.
For many types of communications protocols (e.g., the IEEE 802.15.4 standard protocol), before a node can send a message on a particular channel, the node spends a certain (short) period of time listening for other nodes which might be using the same channel. For example, the 802.15.4 standard specifically uses a type of Carrier Sense Multiple Access-Collision Avoidance (CSMA-CA) algorithm for this “listen-before-talk” process.
However, conventional communications protocols utilized with multi-tier wireless sensor networks experience certain limitations. For example, a common problem often encountered in physically large wireless sensor networks is that there may be two nodes inside the same network and located at two extreme edges of the physical space of that network, which need to send a message at the same moment. If the two nodes are too far apart to hear one another's messages, the nodes may perform the CSMA-CA check and both determine that it is OK to send their respective messages. However, when the two nodes send the messages, other nodes inside the network (most of which are located roughly in between the two extreme nodes) can hear the messages from both of the transmitting nodes. The two messages corrupt one another and thus the nodes in the middle are not able to understand either message. Hence, conventional network protocols are unable to prevent message overlap when not all of the nodes in the network can hear all messages from all other nodes. This is particularly a problem with two end nodes (as opposed to an end node and a gateway or repeater nodes, or two repeater nodes, etc) since end nodes tend to have minimal hardware (e.g. radio transceiver of limited receive sensitivity, and no low-noise amplifier (LNA) for example).
Another general problem in conventional wireless networks relates to the fact that most end-nodes are battery powered, and operate with a low duty cycle, namely the end nodes are in sleep mode a vast majority of the time in order to conserve power. In many cases these low duty cycle nodes “wake up” only when they experience a sensor event (e.g., a motion sensor prompts the awakening of the node). The node then sends any and all appropriate messages and then returns to sleep mode. This leads to a second problem, namely upper-tier management nodes (repeater and gateway nodes) are unable to send network management messages to end-nodes when the end-nodes are in sleep mode a vast majority of the time, such as which channel is currently active. Because an end-node is asleep most of the time, deaf to any management messages from its parent node in the network, and because the end-node wakes up at random times dependent upon events outside of the control of the network, the end node cannot easily track which channel the network is using at any one point in time. Hence, when the end-node does wake up, the conventional approach is for the end-node to conduct a full multi-channel scan to find the network channel in use prior to sending any messages. The full multi-channel scan is extremely expensive from a power perspective. For example, if the network is spending 0.1 seconds on each of 50 channels in pseudo-random hopping, and if the end-node scans backwards in the channel order, it may take 1 or 2 seconds to find the active channel. In accordance with embodiments herein, end-nodes ideally wake up for only a few tenths of a second, a few times per hour or day in order to make coin cell and small rechargeable batteries practical in WSN end-nodes. Hence, a problem exists that end-nodes, after awakening from long periods of sleep, are unable to quickly find the active channel in the network over which the end-nodes are allowed to communicate and waste power finding the active channel. That is, there are cases where end-nodes spend more time and power searching for the active channel in frequency hopping networks than they spend in actually sending and receiving application oriented data.
It is possible that WSNs in the future may one day contain thousands, or perhaps even tens of thousands of end-nodes. The above problems are exacerbated by the sheer number of end-nodes in a very large network, leading to another problem. Conventional network protocols are not well suited to support a very large number of nodes in an extensible way, such as in a way that can theoretically support a nearly unlimited number of end-nodes.
The standard means of avoiding message collision in wireless sensor networks is one of various approaches to “listen-before-talk”, such as the CSMA-CA algorithm of the IEEE 802.15.4 protocol. In one optional implementation (i.e., the beacon mode option), the 802.15.4 protocol enables large networks that use channel slotting in which beacon frames are transmitted at intervals with the time space between beacon frames being divided into a number of time slots. The 802.15.4 standard (version 2, 2006, for example) provides for two types of time slots—time slots in the CAP or “contention access period” and time slots in the CFP or “contention free period”. The latter cannot be used by any node unless the network coordinator node specifically grants access to the time slot. The former can be used by any node provided that node first employs the anti-collision mechanism—CSMA-CA. CSMA-CA and time slotting methods help manage the competition among nodes for a limited bandwidth, but do not scale well when the size of a network substantially increases (e.g., above a few hundred messages per minute). For example, as nodes are added, the number of slots available is quickly exhausted. Also, great pressure is placed on the main node in a large network, and repeater nodes have a relatively limited role of merely repeating the messages between an end-node and the main node. Repeater nodes do not manage protocol values within the repeater node's immediate network (sub-network). Hence, the resulting network does not scale well.
A need remains for an improved WSN that is scalable for use with low duty cycle end nodes.